#include <stdio.h>
#include "tools.h"

void test_char_bit (char c)
{
    bit_print_char(c);
    bit_print_char(~c);
    bit_print_char(-c);
    bit_print_char(c-1);
    
    /* extract the lowest set bit '1' */
    bit_print_char(c & -c);

    /* strip off the lowest bit set */
    bit_print_char(c & (c-1));
}

/*
 * Count the number of bits that are on in an unsigned integer
 */
int count_bit_one_slow (unsigned int x)
{
    int count = 0;

    while (x) {
        count += (x & 0x1u);
        x >>= 1;
    }

    return count;
}

/*
 * It's faster when '1' is sparse
 */
int count_bit_one_sparse (unsigned int x)
{
    int count = 0;

    while (x) {
        count++;
        x &= (x-1);
    }

    return count;
}


/*
 * It's faster when '1' is dense
 */
int count_bit_one_dense (unsigned int x)
{
    unsigned int count = 32;

    x ^= ((unsigned int)-1);

    while (x) {
        count--;
        x &= (x-1);
    }

    return count;
}


int count_bit_one_static (unsigned int x)
{
    static int bits_in_char [256] = {             
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
        3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
        3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
        4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
        3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,
        6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
        4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
        6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
        3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
        4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
        6, 7, 6, 7, 7, 8
    };

    return bits_in_char [x         & 0xffu]
        +  bits_in_char [(x >>  8) & 0xffu]
        +  bits_in_char [(x >> 16) & 0xffu]
        +  bits_in_char [(x >> 24) & 0xffu];
}

unsigned int bit_reverse (unsigned int n)
{
    n = ((n >>  1) & 0x55555555) | ((n <<  1) & 0xaaaaaaaa);
    n = ((n >>  2) & 0x33333333) | ((n <<  2) & 0xcccccccc);
    n = ((n >>  4) & 0x0f0f0f0f) | ((n <<  4) & 0xf0f0f0f0);
    n = ((n >>  8) & 0x00ff00ff) | ((n <<  8) & 0xff00ff00);
    n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);

    return n;
}

int my_sign (int x)
{
    return (-(x<0));
}

int my_abs (int x)
{
    int m = x >> 31;
    bit_print_int(x);
    bit_print_int(m);
    bit_print_int(x^m);
    bit_print_int((x^m) - m);
    
    return ((x^m) - m);
}

int main(int argc, char *argv[])
{
    unsigned int a = 0xabcd3456;
    
    /* test_char_bit(0x2a); */

    bit_print_int(a);
    bit_print_int(bit_reverse(a));
    
    printf("0x%x: %d bit one\n", a, count_bit_one_slow(a));
    printf("0x%x: %d bit one\n", a, count_bit_one_sparse(a));
    printf("0x%x: %d bit one\n", a, count_bit_one_dense(a));
    printf("0x%x: %d bit one\n", a, count_bit_one_static(a));

    printf("abs(%d)=%d\n", -3, my_abs(-3));
    printf("abs(%d)=%d\n", 5, my_abs(5));
    
    return 0;
}
